package code.D1220;

import java.util.*;

/**
 * author： yeswater
 * create： 2023/12/22
 *
 * 除法求值 hashmap +dfs
 */
public class T399 {
    // https://leetcode.cn/problems/evaluate-division/solutions/2320470/javagraphhashmap-dfs-si-lu-qing-xi-jian-vwy2q/
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 初始化 graph
        Map<String, List<Cell>> graph = new HashMap<>();
        // 对于每个 equation 和其结果答案，将其放入 graph
        for (int i = 0; i < values.length; i++) {
            String s1 = equations.get(i).get(0), s2 = equations.get(i).get(1);
            graph.computeIfAbsent(s1, k -> new ArrayList<>()).add(new Cell(s2, values[i]));
            graph.computeIfAbsent(s2, k -> new ArrayList<>()).add(new Cell(s1, 1.0 / values[i]));
        }
        
        // 创建答案 result 数组以及访问过的hashset：visited
        double[] res = new double[queries.size()];
        // 首先将答案中所有答案值置为-1.0，出现（x/x）情况可以不用修改
        Arrays.fill(res, -1.0);
        // 对于每个dfs中的值调位 dfs函数
        for (int i = 0; i < queries.size(); i++) {
            dfs(queries.get(i).get(0), queries.get(i).get(1), 1.0, graph, res, i, new HashSet<>());
        }
        return res;
    }
    
    private void dfs(String src, String dst, double cur, Map<String, List<Cell>> graph, double[] res, int index,Set<String> visited) {
        // base case:在visited中加入当前位置信息；如果加入不了代表已经访问过，直接返回
        if (!visited.add(src)){
            return;
        }
        // 如果当前src = 答案节点dst，并且节点在 graph中 （避免 x/x情况），用当前值cur来填充答案 res
        if (src.equals(dst) && graph.containsKey(src)) {
            res[index] = cur;
            return;
        }
        //对于邻居节点，调整dfs函数
        for (Cell cell : graph.getOrDefault(src, new ArrayList<>())) {
            dfs(cell.str, dst, cur*cell.div, graph, res, index,visited);
        }
    }
    
    private class Cell{
        String str;
        double div;
        
        Cell(String str, double div) {
            this.str = str;
            this.div = div;
        }
    }
}

